This application is related to concurrently filed application Ser. No. 07/259,803 entitled "Framing Algorithm for Bit Interleaved Time Division Multiplexer", which is hereby incorporated by reference herein and which is assigned to the assignee herein. This application is also related to concurrently filed application Ser. No. 07/259,856 entitled "Algorithm for Selecting Channels for Multiplexer Frame", which is assigned to the assignee herein.
The present invention relates to time-division-multiplexed (TDM) telecommunication systems. More particularly, the invention relates to methods for inserting channel selects into a frame wherein the excursions of the channels are minimized.
In multiplexing information from various channels of varying speeds, it is necessary to buffer information from each channel as the receiver of the multiplexer can only attend to one channel at a time. Each channel typically has its own buffer, and the input by the channel into the buffer relative to the output of the buffer to the receiver is typically asynchronous. It is clearly important that the buffers do not become empty of full at any instant as the empty or full condition would indicate duplication or loss of data respectively.
As indicated in Ser. No. 07/259,803, a framing algorithm may be utilized to set the frame length as well as the number of selects from each channel into the frame. It is then necessary to create a time sequence table with entries which define the order in which the receiver responds to the channels. Each entry in the table represents one bit (or in byte systems--one byte) time of the receiver. Each "channel" must have at least one entry in the frame (even if the entry represents a subsidiary frame such as a secondary or tertiary frame), and the frame is repeated at a rate which is the greatest common divisor of the channel rates. In general, some channels have a large number of entries in the table while other channels may have only a few or even a single entry. It is then desirable to space the entries for each channel such that they are an equal distance apart; i.e. to minimize the accumulated deviation (excursion) from the ideal space for the channel selects in the frame.
Two methods for limiting excursion are known in the art. A first method, the "priority method" is to order the channels according to their speed and to start with the fastest channel and place the fastest channel selects as closely as possible to their ideal position. Then, the procedure is repeated for the next highest channel. If the ideal select slot is taken by the previous channel, then the nearest vacant slot is sought. The procedure continues until all of the channel selects are placed in the frame. The obvious disadvantage of the "priority method" scheme is that the slower channels are often moved relatively far away from their ideal slots. A further disadvantage is that considerable iterative effort is required to find and fill vacant slots.
A second method for limiting excursion is described in detail in commonly owned U.S. Pat. No. 4,727,536. In that patent, a real time allocation process is described where the channels are arranged in descending order of channel rates and starting with the fastest channel, the channels are scanned to determine whether they are ready to contribute a bit to the aggregate. Initially, all the channels are considered ready to contribute. After its first contribution to the frame, the readiness of a channel is determined by the position of a counter associated with the channel. The counter is initially set equal to the frame length. Then, each time a bit is inserted into the frame from the highest rate channel which is ready, the position counter of each channel is adjusted by subtracting the number of selects for that channel from the count, and the position counter of the contributing channel is adjusted by adding the frame length value to the counter value. When the position counter reaches zero or goes negative, the channel is marked to be ready to contribute. The procedure of choosing the fastest channel which is ready to contribute continues until the frame is complete such that all the channels have contributed their proportional number of bits.
Although the method of U.S. Pat. No. 4,727,536 is non-iterative and hence efficient, it has some drawbacks in terms of excursion. Unwanted excursion occurs because the method prioritises the channels and tends to be more responsive to the faster channels. In the case of a large number of channels, the non-iterative method can introduce significant excursion to low order channels.